/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
const merge = function (intervals) {
  intervals.sort((a, b) => a[0] - b[0] || a[1] - b[1])
  const res = [intervals[0]]
  for (let i = 1, n = intervals.length; i < n; i++) {
    const [s, e] = intervals[i]
    const pre = res[res.length - 1]
    if (s <= pre[1]) {
      pre[1] = Math.max(pre[1], e)
    } else {
      res.push(intervals[i])
    }
  }
  return res
}

// another

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
const merge = function (intervals) {
  if (intervals == null || intervals.length === 0) return []

  // 按照第一位排序或第二位排序
  intervals.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]))

  const res = [intervals[0]]
  for (let i = 1, n = intervals.length; i < n; i++) {
    // 上一个区间
    const last = res[res.length - 1]
    // 上一个区间的第二位
    const lastEnd = last[1]

    // 当前区间的 第一位、第二位
    const [s, e] = intervals[i]

    // 比较 当前区间第一位 和 上一个区间第二位
    // 如果 大于
    if (s > lastEnd) {
      // 说明区间没有重叠 直接将 当前区间 塞入 结果数组
      res.push(intervals[i])
    } else {
      // 如果 小于等于 说明，区间有重叠，合并区间
      // 注意 上一个区间的 第二位 可能 大于 当前区间的 第二位
      last[1] = Math.max(last[1], e)
    }
  }

  return res
}

// another

/**
 * Definition for an interval.
 * function Interval(start, end) {
 *     this.start = start;
 *     this.end = end;
 * }
 */
/**
 * @param {Interval[]} intervals
 * @return {Interval[]}
 */
const merge = function (intervals) {
  const hash = {}
  intervals.forEach(el => {
    if (hash.hasOwnProperty(el.start)) {
      hash[el.start][1] = Math.max(hash[el.start][1], el.end)
    } else {
      hash[el.start] = [el.start, el.end]
    }
  })

  const startArr = Object.keys(hash).sort((a, b) => +a - +b)
  const res = []

  while (startArr.length) {
    let start = startArr.shift()
    let end = hash[start][1]

    for (let i = 0; i < startArr.length; ) {
      if (+startArr[i] <= end) {
        end = Math.max(end, hash[startArr[i]][1])
        startArr.shift()
      } else {
        break
      }
    }
    let ins = new Interval(+start, end)
    res.push(ins)
  }
  return res
}
